package Ali;

/**
 * 三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，
 * 计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。
 * @author le
 */
public class Test22
{
    public static void main(String[] args)
    {

    }
    public int waysToStep(int n) {
        /*if (n == 1){
            return 1;
        }else if (n == 2){
            return 2;
        }else if (n == 3){
            return 4;
        }else{
            return waysToStep(n-1)+waysToStep(n-2)+waysToStep(n-3);
        }*/

            if(n == 1) {
                return 1;
            }

            if (n == 2) {
                return 2;
            }

            if (n == 3) {
                return 4;
            }

            int dp1 = 1;
            int dp2 = 2;
            int dp3 = 4;
            int dp4 = 0;

            for(int i = 4; i <= n; ++i) {
                dp4 = ((dp1 + dp2) % 1000000007 + dp3) % 1000000007;
                dp1 = dp2;
                dp2 = dp3;
                dp3 = dp4;
            }

            return dp4;

    }
}
